//https://leetcode.cn/problems/selling-pieces-of-wood/?envType=daily-question&envId=2024-03-15


class Solution {
public:
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        int pri[m + 1][n + 1];
        memset(pri, 0, sizeof(pri));
        for (auto a : prices) {
            pri[a[0]][a[1]] = a[2];
        }
        long long dp[m + 1][n + 1];
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i < m + 1; ++i) {
            for (int j = 1; j < n + 1; ++j) {
                dp[i][j] = pri[i][j];
                for (int k = 1; k < j + 1; ++k) {
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]);
                }
                for (int k = 1; k < i + 1; ++k) {
                    dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]);
                }
            }
        }
        return dp[m][n];
    }
};